#define _CRT_SECURE_NO_WARNINGS 1
//int missingNumber(int* nums, int numsSize) {
//    int x = 0;
//    for (int i = 0; i < numsSize; i++)
//    {
//        x ^= nums[i];
//    }
//    for (int i = 0; i < numsSize + 1; i++)
//    {
//        x ^= i;
//    }
//    return x;
//}
//int missingNumber(int* nums, int numsSize) {
//    int x = (1 + numsSize) * numsSize / 2;
//    for (int i = 0; i < numsSize; i++)
//    {
//        x -= nums[i];
//    }
//    return x;
//}
//#include<stdio.h>
//
//int main()
//{
//    int ret = 0;
//    while (~scanf("%d", &ret))
//    {
//        int i = 0;
//        int j = 0;
//        for (i = 0; i < ret; i++)
//        {
//            for (j = 0; j < ret - 1 - i; j++)
//            {
//                printf(" ");
//            }
//            printf("*");
//            printf("\n");
//        }
//    }
//    return 0;
//}
//
//#include<stdio.h>
//
//int main()
//{
//    int ret = 0;
//    while (scanf("%d", &ret) != EOF)
//    {
//        int i = 0;
//        int j = 0;
//        for (i = 0; i < ret; i++)
//        {
//            for (j = 0; j < ret; j++)
//            {
//                if (i + j == ret - 1)
//                {
//                    printf("*");
//                }
//                else {
//                    printf(" ");
//                }
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//
//int main()
//{
//    int ret = 0;
//    while (~scanf("%d", &ret))
//    {
//        int i = 0;
//        int j = 0;
//        for (i = 0; i < ret; i++)
//        {
//            for (j = 0; j < ret; j++)
//            {
//                if ((i + j == ret - 1) || (i == j))
//                {
//                    printf("*");
//                }
//                else {
//                    printf(" ");
//                }
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//
//int main()
//{
//    int ret = 0;
//    while (~scanf("%d", &ret))
//    {
//        int i = 0;
//        int j = 0;
//        for (i = 0; i < ret; i++)
//        {
//            for (j = 0; j < ret; j++)
//            {
//                if ((i >= 1) && (i < ret - 1) && (j >= 1) && (j < ret - 1))
//                {
//                    printf("  ");
//                }
//                else {
//                    printf("* ");
//                }
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//
//int main()
//{
//    int ret = 0;
//    while (~scanf("%d", &ret))
//    {
//        int i = 0;
//        int j = 0;
//        for (i = 0; i < ret; i++)
//        {
//            for (j = 0; j <= i; j++)
//            {
//                if ((i >= 2) && (i < ret - 1) && (j >= 1) && (j < i))
//                {
//                    printf("  ");
//                }
//                else {
//                    printf("* ");
//                }
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}
// 
//void reverse(int* p1, int* p2)
//{
//
//    while (p1 <= p2)
//    {
//        int tmp = *p1;
//        *p1 = *p2;
//        *p2 = tmp;
//        p1++;
//        p2--;
//    }
//}
//void rotate(int* nums, int numsSize, int k) {
//    if (k > numsSize)
//    {
//        k %= numsSize;
//    }
//    reverse(nums, nums + numsSize - 1 - k);
//    reverse(nums + numsSize - k, nums + numsSize - 1);
//    reverse(nums, nums + numsSize - 1);
//}